// Source file:
// G:\\5o_ano\\PCS2040\\desenvolvimento\\rose\\Servidor\\Roteamento\\Grafo.java

package servidor.roteamento;

import java.util.ArrayList;
import java.util.Iterator;

public class Grafo {

    private ArrayList vertices;
    private int nivelHierarquico;
    private String nome;
    
    private VerticeSubMapa verticeQueContem;

    /**
     * @roseuid 426D7C500119
     */
    public Grafo(String nome, int nivelHierarquico) {
        vertices = new ArrayList();
        this.nivelHierarquico = nivelHierarquico;
        this.nome = nome;
    }

    /**
     * @roseuid 42599F2801C5
     */
    public boolean addVertice(Vertice v) {
        return vertices.add(v);
    }

    /**
     * @roseuid 42599F2F0167
     */
    public Vertice getVertice(String nome) {
        for (Iterator iter = vertices.iterator(); iter.hasNext();) {
            Vertice vertice = (Vertice) iter.next();
            if (vertice.getNome().equals(nome)) {
                return vertice;
            }
        }
        return null;
    }
    
    public Vertice getVerticeFrom(int id) {
        for (Iterator iter = vertices.iterator(); iter.hasNext();) {
            Vertice vertice = (Vertice) iter.next();
            if (vertice.getNome().equals(nome)) {
                return vertice;
            }
        }
        return null;
    }    
    
    /**
     * Retorna o vertices.
     * @return vertices
     */
    public ArrayList getVertices() {
        return vertices;
    }
    
    /**
     * @roseuid 426033D4009C
     */
    public int getNivelHierarquico() {
        return nivelHierarquico;
    }

    /**
     * @return Returns the nome.
     */
    public String getNome() {
        return nome;
    }
    
	/**
	 * @return Returns the verticeQueContem.
	 */
	public VerticeSubMapa getVerticeQueContem() {
		return verticeQueContem;
	}
	/**
	 * @param verticeQueContem The verticeQueContem to set.
	 */
	public void setVerticeQueContem(VerticeSubMapa verticeQueContem) {
		this.verticeQueContem = verticeQueContem;
	}
	
	
    public Caminho busca(Vertice origem, Vertice destino, int restricao) {
        ArrayList open = new ArrayList();
        ArrayList closed = new ArrayList();
        Caminho caminhoDesejado = null;

        Caminho caminho = new Caminho();
        caminho.add(origem, 0);
        open.add(caminho);

        while (open.size() != 0) {
            caminho = (Caminho) open.remove(0);
            closed.add(caminho);
            if (caminho.getFinal().equals(destino)) {
                if (caminhoDesejado == null) {
                    caminhoDesejado = caminho;
                } else {
                    if (caminho.getCusto() < caminhoDesejado.getCusto()) {
                        caminhoDesejado = caminho;
                    }
                }
            } else {
                Vertice v = caminho.getFinal();
                ArrayList array = v.getVerticesAdjacentes();
                for (int i = 0; i < array.size(); i++) {
                    Vertice novoVertice = ((VerticeAdjacente) array.get(i)).getVertice();
                    Caminho original = null;
                    for (int j = 0; j < closed.size(); j++) {
                        Caminho c = (Caminho) closed.get(j);
                        if (c.getFinal().equals(novoVertice)) {
                            original = c;
                        }
                    }
                    Caminho c = new Caminho(caminho);
                    int[] custos = ((VerticeAdjacente) array.get(i)).getCustos();
                    c.add(novoVertice, custos[restricao]);
                    if (original == null) {
                        open.add(c);
                    } else { //se j� existe um caminho para aquele vertice
                        //compara��o dos custos dos dois caminhos...
                        double custoOriginal = original.getCusto();
                        double custoNovo = c.getCusto();
                        if (custoNovo < custoOriginal) {
                            closed.remove(original);
                            open.add(c);
                        }
                    }
                }
            }
        }
        return caminhoDesejado;
    }

}